import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main{
    public static void main(String[] args) {
        Solution.TreeNode A = new Solution.TreeNode('A');
        Solution.TreeNode B = new Solution.TreeNode('B');
        Solution.TreeNode C = new Solution.TreeNode('C');
        Solution.TreeNode D = new Solution.TreeNode('D');
        Solution.TreeNode E = new Solution.TreeNode('E');
        Solution.TreeNode F = new Solution.TreeNode('F');


        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = null;

        D.left = null;
        D.right = null;
        E.left = null;
        E.right = null;
        F.left = null;
        F.right = null;

        boolean ok = Solution.isCompleteTree(A);
    }
}

class Solution {
    public static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(char val) { this.val = val; }
        TreeNode(char val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // 判断二叉树是否相同
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }
        //结构不同(一棵空，一棵非空)
        else if((p == null && q != null) || (p != null && q == null)){
            return false;
        }
        // 都非空
        else{
            // 值不同
            if(p.val != q.val){
                return false;
            }
            // 值相同
            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        }
    }


    // 中序遍历打印二叉树
    public static void levelOrder(TreeNode root){
        // 1、空树
        if (root == null){
            return;
        }

        // 2、非空
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(root);
        while (!qu.isEmpty()){
            TreeNode tmp = qu.poll();
            System.out.print(tmp.val + " ");

            if(tmp.left != null){
                qu.offer(tmp.left);
            }
            if (tmp.right != null){
                qu.offer(tmp.right);
            }
        }
    }

    // 中序遍历并返回结果集(LeetCode刷题)
    public static List<List<Integer>> levelOrder1(TreeNode root) {
        //0、准备返回值
        List<List<Integer>> lists = new ArrayList<>();
        // 1、空树
        if (root == null){
            return lists;
        }
        // 2、非空
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            // 3、计算此时队列里有多少个元素
            int cnt = queue.size();

            // 4、把队列里的元素拿出一个，再把这个元素的左右子树的根入队列
            // 循环直到这一层的元素全从队列拿出来(以cnt=0为结束标志)
            List<Integer> list = new ArrayList<>();
            while(cnt > 0){
                TreeNode out = queue.poll();
                if(out != null){
                    list.add(Integer.valueOf(out.val));
                }

                // 注意：out的左右子树的根不为空，则入队
                if(out.left != null){
                    queue.offer(out.left);
                }
                if(out.right != null){
                    queue.offer(out.right);
                }
                cnt--;
            }

            lists.add(list);
        }

        // 、返回类似于二维数组的集合
        return lists;
    }


    // 判断一棵树是不是完全二叉树
    public static boolean isCompleteTree(TreeNode root){
        // 1、空树
        if (root == null){
            return false;
        }

        // 2、非空
        Queue<TreeNode> qu = new LinkedList<>();
        qu.offer(root);
        while (!qu.isEmpty()){
            // 3、把树的所有节点包括叶子结点的null，按照层序遍历的方式入队列
            TreeNode cur = qu.poll();
            if (cur != null){
                qu.offer(cur.left);
                qu.offer(cur.right);
            }else{
                break;
            }
        }

        // 特别注意：程序进行到这里，必定是从上面循环break出来的，即出队元素遇到了null,所以退出循环
        //   4、这里要做的就是判断队列剩下的元素中是否有非null元素，有非nill元素则返回false;
        while(!qu.isEmpty()){
            if(qu.poll() != null){
                return false;
            }
        }

        // 5、不断出队，最后队列为空了，也还没返回false，则是完全二叉树，返回true。
        return true;
    }
}